{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Find the Longest Valid Obstacle Course at Each Position"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Hard"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #binary-indexed-tree #array #binary-search"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #树状数组 #数组 #二分查找"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: longestObstacleCourseAtEachPosition"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #找出到每个位置为止最长的有效障碍赛跑路线"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>你打算构建一些障碍赛跑路线。给你一个 <strong>下标从 0 开始</strong> 的整数数组 <code>obstacles</code> ，数组长度为 <code>n</code> ，其中 <code>obstacles[i]</code> 表示第 <code>i</code> 个障碍的高度。</p>\n",
    "\n",
    "<p>对于每个介于 <code>0</code> 和 <code>n - 1</code> 之间（包含 <code>0</code> 和 <code>n - 1</code>）的下标&nbsp; <code>i</code> ，在满足下述条件的前提下，请你找出&nbsp;<code>obstacles</code> 能构成的最长障碍路线的长度：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li>你可以选择下标介于 <code>0</code> 到 <code>i</code> 之间（包含 <code>0</code> 和 <code>i</code>）的任意个障碍。</li>\n",
    "\t<li>在这条路线中，必须包含第 <code>i</code> 个障碍。</li>\n",
    "\t<li>你必须按障碍在&nbsp;<code>obstacles</code>&nbsp;中的<strong> </strong><strong>出现顺序</strong> 布置这些障碍。</li>\n",
    "\t<li>除第一个障碍外，路线中每个障碍的高度都必须和前一个障碍 <strong>相同</strong> 或者 <strong>更高</strong> 。</li>\n",
    "</ul>\n",
    "\n",
    "<p>返回长度为 <code>n</code> 的答案数组 <code>ans</code> ，其中 <code>ans[i]</code> 是上面所述的下标 <code>i</code> 对应的最长障碍赛跑路线的长度。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>obstacles = [1,2,3,2]\n",
    "<strong>输出：</strong>[1,2,3,3]\n",
    "<strong>解释：</strong>每个位置的最长有效障碍路线是：\n",
    "- i = 0: [<em><strong>1</strong></em>], [1] 长度为 1\n",
    "- i = 1: [<em><strong>1</strong></em>,<em><strong>2</strong></em>], [1,2] 长度为 2\n",
    "- i = 2: [<em><strong>1</strong></em>,<em><strong>2</strong></em>,<em><strong>3</strong></em>], [1,2,3] 长度为 3\n",
    "- i = 3: [<em><strong>1</strong></em>,<em><strong>2</strong></em>,3,<em><strong>2</strong></em>], [1,2,2] 长度为 3\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>obstacles = [2,2,1]\n",
    "<strong>输出：</strong>[1,2,1]\n",
    "<strong>解释：</strong>每个位置的最长有效障碍路线是：\n",
    "- i = 0: [<em><strong>2</strong></em>], [2] 长度为 1\n",
    "- i = 1: [<em><strong>2</strong></em>,<em><strong>2</strong></em>], [2,2] 长度为 2\n",
    "- i = 2: [2,2,<em><strong>1</strong></em>], [1] 长度为 1\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>obstacles = [3,1,5,6,4,2]\n",
    "<strong>输出：</strong>[1,1,2,3,2,2]\n",
    "<strong>解释：</strong>每个位置的最长有效障碍路线是：\n",
    "- i = 0: [<em><strong>3</strong></em>], [3] 长度为 1\n",
    "- i = 1: [3,<em><strong>1</strong></em>], [1] 长度为 1\n",
    "- i = 2: [<em><strong>3</strong></em>,1,<em><strong>5</strong></em>], [3,5] 长度为 2, [1,5] 也是有效的障碍赛跑路线\n",
    "- i = 3: [<em><strong>3</strong></em>,1,<em><strong>5</strong></em>,<em><strong>6</strong></em>], [3,5,6] 长度为 3, [1,5,6] 也是有效的障碍赛跑路线\n",
    "- i = 4: [<em><strong>3</strong></em>,1,5,6,<em><strong>4</strong></em>], [3,4] 长度为 2, [1,4] 也是有效的障碍赛跑路线\n",
    "- i = 5: [3,<em><strong>1</strong></em>,5,6,4,<em><strong>2</strong></em>], [1,2] 长度为 2\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>n == obstacles.length</code></li>\n",
    "\t<li><code>1 &lt;= n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= obstacles[i] &lt;= 10<sup>7</sup></code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [find-the-longest-valid-obstacle-course-at-each-position](https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [find-the-longest-valid-obstacle-course-at-each-position](https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[1,2,3,2]', '[2,2,1]', '[3,1,5,6,4,2]']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 二分查找，找到更新值，找不到追加\n",
    "        def search_update(target:int):\n",
    "            low = 0\n",
    "            high=len(levels)-1\n",
    "            result = -1  \n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if levels[mid] > target:\n",
    "                    result = mid  # 找到大于目标值的位置，更新结果\n",
    "                    high = mid - 1  # 继续在左半部分查找\n",
    "                else:\n",
    "                    low = mid + 1  # 在右半部分查找\n",
    "            if result==-1:\n",
    "                #没找到追加,记录层级，层级正好是数组的长度\n",
    "                levels.append(target)\n",
    "                dp[i]=len(levels)\n",
    "            else:\n",
    "                #找到则更新，记录当前层级\n",
    "                levels[result]=target\n",
    "                dp[i]=result+1\n",
    "\n",
    "        n=len(obstacles)\n",
    "        # 默认至少有1，也是为后续循环从1开始，设置0位置的初始值\n",
    "        dp=[1]*n\n",
    "        levels=[obstacles[0]]\n",
    "        for i in range(1,n):\n",
    "            lvl=search_update(obstacles[i])\n",
    "        return dp\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        dp = [0] * (n + 1)\n",
    "        dp[0] = obstacles[0]\n",
    "        ret = [0] * n\n",
    "        ret[0] = 1\n",
    "        idx = 1\n",
    "        for i in range(1, n):\n",
    "            l, r = 0, idx - 1\n",
    "            while l <= r:\n",
    "                m = l + r >> 1\n",
    "                if dp[m] <= obstacles[i]:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m - 1\n",
    "            if l == idx:\n",
    "                idx += 1\n",
    "            dp[l] = obstacles[i]\n",
    "            \n",
    "            ret[i] = l + 1\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        ans = [1]\n",
    "        tail = [0] * n\n",
    "        tail[0] = obstacles[0]\n",
    "        r = 1\n",
    "        for i in range(1, n):\n",
    "            idx = bisect.bisect_right(tail, obstacles[i], 0, r)\n",
    "            tail[idx] = obstacles[i]\n",
    "            if idx == r:\n",
    "                r += 1\n",
    "            ans.append(idx + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        d = [inf] * n\n",
    "        cnt = [0] * n\n",
    "        for i in range(n):\n",
    "            obstacle = obstacles[i]\n",
    "            loc = bisect_right(d, obstacle, 0, i)\n",
    "            d[loc] = obstacle\n",
    "            cnt[i] = loc + 1\n",
    "        return cnt\n",
    "        \n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        def LIS(A):\n",
    "            d = []\n",
    "            ans = []\n",
    "            for a in A:\n",
    "                i = bisect.bisect_right(d, a)\n",
    "                if d and i < len(d):\n",
    "                    d[i] = a\n",
    "                else:\n",
    "                    d.append(a)\n",
    "                ans.append(i+1)\n",
    "            return ans\n",
    "        return LIS(obstacles)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        n = len(obstacles)\n",
    "        min_end = [0]\n",
    "        for v in obstacles:\n",
    "            l, r = 0, len(min_end) - 1\n",
    "            while l < r:\n",
    "                mid = l + (r - l + 1) // 2\n",
    "                if min_end[mid] <= v:\n",
    "                    l = mid\n",
    "                else:\n",
    "                    r = mid - 1\n",
    "            ans.append(l + 1)\n",
    "            if l + 1 >= len(min_end):\n",
    "                min_end.append(v)\n",
    "            else:\n",
    "                min_end[l+1] = min(min_end[l+1], v)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # n = len(obstacles)\n",
    "        # dp= [1] * n\n",
    "        # for i in range(1, n):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[i]>=obstacles[j]:\n",
    "        #             dp[i] = max(dp[i], dp[j]+1)\n",
    "\n",
    "        # return dp\n",
    "\n",
    "        n = len(obstacles)\n",
    "        mem = []\n",
    "        temp_l = 1\n",
    "        res = [1]*n\n",
    "        for i, v in enumerate(obstacles):\n",
    "            if not mem or mem[-1]<=v:\n",
    "                mem.append(v)\n",
    "                res[i] = len(mem)\n",
    "            else:\n",
    "                left, right = 0, len(mem)-1\n",
    "                while left<=right:\n",
    "                    mid = (left+right)//2\n",
    "                    if mem[mid]>v:\n",
    "                        right = mid-1\n",
    "                    else:\n",
    "                        left = mid+1\n",
    "                # print(mem, left, v)\n",
    "                mem[left] = v\n",
    "                res[i] = left+1\n",
    "        return res\n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        res = [1]\n",
    "        d = [obstacles[0]]\n",
    "        l = 1\n",
    "        for i in range(1, len(obstacles)):\n",
    "            if obstacles[i] >= d[-1]:\n",
    "                d.append(obstacles[i])\n",
    "                l += 1\n",
    "                res.append(l)\n",
    "            else:\n",
    "                index = bisect_right(d, obstacles[i])\n",
    "                res.append(index + 1)\n",
    "                d[index] = obstacles[i]\n",
    "        return res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        ng = 0\n",
    "        for i,x in enumerate(obstacles):\n",
    "            idx = bisect_right(obstacles,x,0,ng)\n",
    "            if idx == ng:\n",
    "                ng += 1\n",
    "                ans.append(ng)\n",
    "            else:\n",
    "                ans.append(idx + 1)\n",
    "            obstacles[idx] = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        stack = []\n",
    "        for num in obstacles:\n",
    "            if not stack or stack[-1] <= num:\n",
    "                stack.append(num)\n",
    "                ans.append(len(stack))\n",
    "            else:\n",
    "                idx = bisect.bisect_right(stack, num)\n",
    "                stack[idx] = num\n",
    "                ans.append(idx + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        def search_update(arr: List[int],high:int ,target:int):\n",
    "            result = high  \n",
    "            low = 0\n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if arr[mid] > target:\n",
    "                    result = mid  # 找到大于目标值的位置，更新结果\n",
    "                    high = mid - 1  # 继续在左半部分查找\n",
    "                else:\n",
    "                    low = mid + 1  # 在右半部分查找\n",
    "            arr[result]=target\n",
    "            return result\n",
    "\n",
    "        n=len(obstacles)\n",
    "        dp=[0]*n\n",
    "        min_level=[0]*n\n",
    "        max_lvl=-1\n",
    "        for i in range(n):\n",
    "            lvl=search_update(min_level,max_lvl+1,obstacles[i])\n",
    "            max_lvl=max(max_lvl,lvl)\n",
    "            dp[i]=lvl+1\n",
    "        return dp\n",
    "        \n",
    "                \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 求以 obstacles[i] 结尾的最长非递减子序列的长度\n",
    "        # 空间优化\n",
    "        g_l = 0\n",
    "        ans = []\n",
    "        for x in obstacles:\n",
    "            j = bisect_right(obstacles, x, 0, g_l)\n",
    "            ans.append(j + 1)\n",
    "            obstacles[j] = x\n",
    "            if j == g_l:\n",
    "                g_l += 1\n",
    "        return ans\n",
    "        \n",
    "        # 贪心 + 二分\n",
    "        # g = []\n",
    "        # ans = []\n",
    "        # for x in obstacles:\n",
    "        #     j = bisect_right(g, x)\n",
    "        #     ans.append(j + 1)\n",
    "        #     if j == len(g):\n",
    "        #         g.append(x)\n",
    "        #     else:\n",
    "        #         g[j] = x\n",
    "        # return ans\n",
    "\n",
    "\n",
    "        # 递推 O(n ** 2) TLE\n",
    "        # n = len(obstacles)\n",
    "        # f = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j] <= obstacles[i]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += 1\n",
    "        # return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution(object):\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles):\n",
    "        \"\"\"\n",
    "        :type obstacles: List[int]\n",
    "        :rtype: List[int]\n",
    "        \"\"\"\n",
    "        tlen=len(obstacles)\n",
    "        res=[1]*tlen\n",
    "        f = [obstacles[0]]\n",
    "        for i in range(1, tlen):\n",
    "            if (num := obstacles[i]) >= f[-1]:\n",
    "                f.append(num)\n",
    "                res[i]=len(f)\n",
    "            else:\n",
    "                index = bisect_right(f, num)\n",
    "                f[index] = min(num,f[index])\n",
    "                res[i]=index+1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = [0] * l\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp[i] = right + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = [0] * l\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            if 0 < i < len(obstacles) - 1 and obstacles[i] == obstacles[i - 1]:\n",
    "                right += 1\n",
    "            else:\n",
    "                right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp[i] = right + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = [0] * l\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp[i] = right + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        tails = [0] * n\n",
    "        result = []\n",
    "        res = 0\n",
    "        for num in obstacles:\n",
    "            i, j = 0, res\n",
    "            while i < j:\n",
    "                m = (i+j) // 2\n",
    "                if tails[m] <= num: i = m+1\n",
    "                else: j = m\n",
    "            tails[i] = num\n",
    "            if j == res: \n",
    "                res +=1\n",
    "                result.append(res)\n",
    "            else:\n",
    "                result.append(i+1)\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        if not obstacles or len(obstacles) == 0:\n",
    "            return []\n",
    "        n = len(obstacles)\n",
    "        res = [1] * n\n",
    "        save = [obstacles[0]]\n",
    "        for i in range(1, n):\n",
    "            if obstacles[i] >= save[-1]:\n",
    "                save.append(obstacles[i])\n",
    "                res[i] = len(save)\n",
    "                pass\n",
    "            else:\n",
    "                index = bisect.bisect_right(save, obstacles[i])\n",
    "                save[index] = obstacles[i]\n",
    "                res[i] = index + 1\n",
    "                pass\n",
    "            pass\n",
    "        return res\n",
    "    pass\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     res = 0\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j] <= obstacles[i]:\n",
    "        #             res = max(res,dfs(j))\n",
    "        #     return res + 1\n",
    "        # return [dfs(i) for i in range(n)]\n",
    "\n",
    "        # ans = [0] * n\n",
    "        # for i,x in enumerate(obstacles):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j]<=obstacles[i]:\n",
    "        #             ans[i] = max(ans[i],ans[j])\n",
    "        #     ans[i] += 1\n",
    "        # return ans\n",
    "        ans = [0] * n\n",
    "        g = []\n",
    "        for i,x in enumerate(obstacles):\n",
    "            j = bisect.bisect_right(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "            ans[i] = j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        dp = [1] * len(obstacles)\n",
    "        arr = [obstacles[0]]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            if obstacles[i]>= arr[-1]:\n",
    "                arr.append(obstacles[i])\n",
    "                dp[i] = len(arr)\n",
    "            else:\n",
    "                pos = bisect.bisect_right(arr,obstacles[i])\n",
    "                arr[pos] = obstacles[i]\n",
    "                dp[i] = pos +1 \n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        g = []\n",
    "        ans = [0] * n\n",
    "        for i in range(n):\n",
    "            index = bisect.bisect_right(g, obstacles[i])\n",
    "            if index == len(g):\n",
    "                g.append(obstacles[i])\n",
    "                ans[i] = len(g)\n",
    "            else:\n",
    "                g[index] = obstacles[i]\n",
    "                ans[i] = index + 1\n",
    "        return ans\n",
    "\n",
    "        # dp = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     dp[i] = max((dp[j] for j in range(i) if obstacles[j] <= obstacles[i]), default = 0) + 1\n",
    "        # return dp\n",
    "\n",
    "        # @cache\n",
    "        # def dfs(i: int) -> int:\n",
    "        #     return max((dfs(j) for j in range(i) if obstacles[j] <= obstacles[i]), default = 0) + 1\n",
    "        # return [dfs(i) for i in range(n)]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = [0] * l\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp[i] = right + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     if i < 0:\n",
    "        #         return 0\n",
    "        #     res = 0\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j] <= obstacles[i]:\n",
    "        #             res = max(res,dfs(j))\n",
    "        #     return res + 1\n",
    "        # return [dfs(i) for i in range(n)]\n",
    "\n",
    "        # ans = [0] * n\n",
    "        # for i,x in enumerate(obstacles):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j]<=obstacles[i]:\n",
    "        #             ans[i] = max(ans[i],ans[j])\n",
    "        #     ans[i] += 1\n",
    "        # return ans\n",
    "        ans = [0] * n\n",
    "        g = []\n",
    "        for i,x in enumerate(obstacles):\n",
    "            j = bisect_right(g,x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "            ans[i] = j + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = [0] * l\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp[i] = right + 1\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 二分查找，找到更新值，找不到追加\n",
    "        def search_update(target:int):\n",
    "            low = 0\n",
    "            high=len(levels)-1\n",
    "            result = -1  \n",
    "            while low <= high:\n",
    "                mid = (low + high) // 2\n",
    "                if levels[mid] > target:\n",
    "                    result = mid  # 找到大于目标值的位置，更新结果\n",
    "                    high = mid - 1  # 继续在左半部分查找\n",
    "                else:\n",
    "                    low = mid + 1  # 在右半部分查找\n",
    "            if result==-1:\n",
    "                #没找到追加,记录层级，层级正好是数组的长度\n",
    "                levels.append(target)\n",
    "                dp[i]=len(levels)\n",
    "            else:\n",
    "                #找到则更新，记录当前层级\n",
    "                levels[result]=target\n",
    "                dp[i]=result+1\n",
    "\n",
    "        n=len(obstacles)\n",
    "        # 默认至少有1，也是为后续循环从1开始，设置0位置的初始值\n",
    "        dp=[1]*n\n",
    "        levels=[obstacles[0]]\n",
    "        for i in range(1,n):\n",
    "            lvl=search_update(obstacles[i])\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n=len(obstacles)\n",
    "        dp=[1]*n\n",
    "        f=[obstacles[0]]\n",
    "        for i in range(1,n):\n",
    "            num=obstacles[i]\n",
    "            if num>=f[-1]:\n",
    "                f.append(num)\n",
    "                dp[i]=len(f)\n",
    "            else:\n",
    "                index=bisect.bisect_right(f,num)\n",
    "                f[index]=num\n",
    "                dp[i]=index+1\n",
    "        print(f)\n",
    "        return dp\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        tails = [0] * n\n",
    "        subMax = 0\n",
    "        res = []\n",
    "\n",
    "        for ob in obstacles:\n",
    "            i, j = 0, subMax\n",
    "            while i < j:\n",
    "                mid = i + ((j-i) >> 1)\n",
    "                if tails[mid] <= ob:\n",
    "                    i = mid + 1\n",
    "                else:  #找到大于ob的最小索引(相等也往前走，允许相同的存在)\n",
    "                    j = mid\n",
    "            tails[j] = ob\n",
    "            res.append(j+1)\n",
    "            if j == subMax: subMax += 1\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = []\n",
    "        ans = []\n",
    "        for n in obstacles:\n",
    "            if not d or n >= d[-1]:\n",
    "                d.append(n)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                l, r = 0, len(d) - 1\n",
    "                while l < r:\n",
    "                    mid = (l + r) // 2\n",
    "                    if d[mid] > n:\n",
    "                        r = mid\n",
    "                    else:\n",
    "                        l = mid + 1\n",
    "                d[l] = n\n",
    "                ans.append(l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n=len(obstacles)\n",
    "        dp=[inf]*(n+1)\n",
    "        t=0;res=[]\n",
    "        for x in obstacles:\n",
    "            l=0;r=n\n",
    "            while l<r:\n",
    "                mid=l+r+1>>1\n",
    "                if dp[mid]>x: r=mid-1\n",
    "                else: l=mid\n",
    "            dp[l+1]=x\n",
    "            res.append(l+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n=len(obstacles)\n",
    "        ans=[1]\n",
    "        d=[obstacles[0]]\n",
    "        for i,x in enumerate(obstacles[1:]):\n",
    "            if x>=d[-1]:\n",
    "                d.append(x)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                index=bisect_right(d,x)\n",
    "                d[index]=x\n",
    "                ans.append(index+1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = []\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            right = bisect_right(ma, obstacles[i])\n",
    "            ma[right] = obstacles[i]\n",
    "            dp.append(right + 1)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = list()\n",
    "        g = list()\n",
    "        for i in obstacles:\n",
    "\n",
    "\n",
    "            if not g or i >= g[-1]:\n",
    "                g.append(i)\n",
    "                ans.append(len(g))\n",
    "            else:\n",
    "                left, right = 0, len(g) - 1\n",
    "                while left <= right:\n",
    "                    mid = (left + right) // 2\n",
    "                    if i >= g[mid]:\n",
    "                        left = mid + 1\n",
    "                    else:\n",
    "                        right = mid - 1\n",
    "                ans.append(left + 1)\n",
    "                g[left] = i\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "\n",
    "        # n = len(obstacles)\n",
    "        # f = [0] * n\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[i] >= obstacles[j]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += 1\n",
    "        # return f\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     ans = 0\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[i] >= obstacles[j]:\n",
    "        #             ans = max(ans, dfs(j))\n",
    "        #     ans += 1\n",
    "        #     return ans\n",
    "        \n",
    "        # return [dfs(i) for i in range(n)]\n",
    "        \n",
    "        n = len(obstacles)\n",
    "        f = [0] * n\n",
    "        g = []\n",
    "        for i, x in enumerate(obstacles):\n",
    "            j = bisect_right(g, x)\n",
    "            if j == len(g):\n",
    "                f[i] = len(g) + 1\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "                f[i] = j+1\n",
    "        return f"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from math import *\n",
    "from queue import PriorityQueue\n",
    "from typing import *\n",
    "from heapq import *\n",
    "from functools import lru_cache\n",
    "# by hangpengjie\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        d = []\n",
    "        for ob in obstacles:\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "                continue\n",
    "            l,r = 0, len(d)-1\n",
    "            while l < r:\n",
    "                m = (l + r) >> 1\n",
    "                if d[m] <= ob:\n",
    "                    l = m + 1\n",
    "                else:\n",
    "                    r = m\n",
    "            d[l] = ob\n",
    "            ans.append(l + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        dp =  [1] *(n)\n",
    "        s = []\n",
    "        for i, num in enumerate(nums):\n",
    "            l, r = 0, len(s)\n",
    "            while l < r:\n",
    "                m = (l+r)>>1\n",
    "                if s[m] <= num:\n",
    "                    l = m+1\n",
    "                else:\n",
    "                    r = m\n",
    "            if l == len(s):\n",
    "                s.append(num)\n",
    "            s[l] = num\n",
    "            dp[i] = l + 1\n",
    "        return dp\n",
    "\n",
    "# dp[i] 表示nums[:i]包含nums[i] 路线最大值\n",
    "# dp[i] = max{dp[j] + 1}, j < i and nums[j] <= nums[i]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        ans = [0] * n\n",
    "        end = [0]\n",
    "        for i,v in enumerate(obstacles):\n",
    "            if v >= end[-1]:\n",
    "                end.append(v)\n",
    "                ans[i] = len(end) - 1\n",
    "            else:\n",
    "                p = bisect_right(end, v)\n",
    "                ans[i] = p\n",
    "                end[p] = v\n",
    "            # print(i,v, end)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n=len(obstacles)\n",
    "        dp=[inf]*(n+1)\n",
    "        t=0;res=[0]*n\n",
    "        for i,x in enumerate(obstacles):\n",
    "            l=0;r=n\n",
    "            while l<r:\n",
    "                mid=l+r+1>>1\n",
    "                if dp[mid]>x: r=mid-1\n",
    "                else: l=mid\n",
    "            dp[l+1]=x\n",
    "            res[i]=l+1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        l = len(obstacles)\n",
    "        dp = []\n",
    "        ma = [max(obstacles) + 1] * l\n",
    "        for i in range(len(obstacles)):\n",
    "            if 0 < i < len(obstacles) - 1 and obstacles[i] == obstacles[i - 1]:\n",
    "                right += 1\n",
    "                ma[right] = obstacles[i]\n",
    "            else:\n",
    "                left = bisect.bisect_left(ma, obstacles[i])\n",
    "                right = bisect.bisect_right(ma, obstacles[i])\n",
    "                for j in range(left, right + 1):\n",
    "                    ma[j] = obstacles[i]\n",
    "            dp.append(right + 1)\n",
    "        return dp"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.method = 1\n",
    "\n",
    "        if self.method == 1:\n",
    "            print(\"BINARY_SEARCH\")\n",
    "        elif self.method == 2:\n",
    "            print(\"DYNAMIC_PROGRAMMING: Time Limit Exceeded\")\n",
    "        print()\n",
    "\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        retVal = []\n",
    "\n",
    "        if self.method == 1:\n",
    "            greedy = []\n",
    "            for obstacle in obstacles:\n",
    "                if not greedy or obstacle >= greedy[-1]:\n",
    "                    greedy.append(obstacle)\n",
    "                    retVal.append(len(greedy))\n",
    "                else:\n",
    "                    position = bisect_right(greedy, obstacle)\n",
    "                    retVal.append(position + 1)\n",
    "                    greedy[position] = obstacle\n",
    "        elif self.method == 2:\n",
    "            obstaclesSize = len(obstacles)\n",
    "            dp = [1] * obstaclesSize\n",
    "            for i in range(obstaclesSize):\n",
    "                for j in range(i):\n",
    "                    if (obstacles[j] <= obstacles[i]):\n",
    "                        dp[i] = max(dp[i], dp[j] + 1)\n",
    "            retVal = dp\n",
    "\n",
    "        return retVal"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        dp, ans = [], [0] * n\n",
    "        # dp[j]表示前i个数长度为j的最长非严格上升子序列结尾的最小值\n",
    "        dp.append(obstacles[0])\n",
    "        ans[0] = 1\n",
    "        for i, x in enumerate(obstacles):\n",
    "            if not i: continue\n",
    "            if dp[-1] <= x:\n",
    "                dp.append(x)\n",
    "                ans[i] = len(dp)\n",
    "            else: # nums[i] < x < nums[i + 1]\n",
    "                idx = bisect.bisect_right(dp, x)\n",
    "                ans[i] = idx + 1\n",
    "                dp[idx] = x\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 每一个下标i含，之前最长的非递减序列长度\n",
    "        n = len(obstacles)\n",
    "        ans = [1] * n\n",
    "        lis = []\n",
    "        \n",
    "        for i, obstacle in enumerate(obstacles):\n",
    "            idx = bisect_right(lis, obstacle)\n",
    "            if not lis or obstacle >= lis[-1]:\n",
    "                lis.append(obstacle)\n",
    "                ans[i] = len(lis)\n",
    "            else:\n",
    "                idx = bisect_right(lis, obstacle)\n",
    "                lis[idx] = obstacle\n",
    "                ans[i] = idx + 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # length = len(obstacles)\n",
    "        # res = []\n",
    "        # dp = [1] * length\n",
    "        # for i in range(length):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[i] >= obstacles[j]:\n",
    "        #             dp[i] = max(dp[j]+1, dp[i])\n",
    "        #     res.append(dp[i])\n",
    "        # return res\n",
    "        res = [obstacles[0]]\n",
    "        record = [1]\n",
    "        for i in obstacles[1:]:\n",
    "            if i >= res[-1]:\n",
    "                res.append(i)\n",
    "                record.append(len(res))\n",
    "            else:\n",
    "                index = bisect_right(res, i)\n",
    "                res[index] = i\n",
    "                record.append(index+1)\n",
    "        return record\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        length_sub = [1 for i in range(len(obstacles))]\n",
    "        record = [obstacles[0]]\n",
    "        for i in range(1,len(obstacles)):\n",
    "            if obstacles[i]>=record[-1]:\n",
    "                record.append(obstacles[i])\n",
    "                length_sub[i] = len(record)\n",
    "            else:\n",
    "                start, end = 0, len(record)-1\n",
    "                while start<end:\n",
    "                    mid = (start+end)//2\n",
    "                    if record[mid] > obstacles[i]:\n",
    "                        end = mid\n",
    "                    else:\n",
    "                        start = mid+1\n",
    "                record[start] = obstacles[i]\n",
    "                length_sub[i] = start+1\n",
    "        return length_sub\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        g = []\n",
    "        ret = []\n",
    "        for x in obstacles:\n",
    "            j = bisect_right(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "                ret.append(len(g))\n",
    "            else:\n",
    "                g[j] = x\n",
    "                ret.append(j+1)\n",
    "        return ret"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = [obstacles[0]]\n",
    "        ans = [1]\n",
    "        for o in obstacles[1:]:\n",
    "            if o >= d[-1]:\n",
    "                d.append(o)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                idx = bisect.bisect(d, o)\n",
    "                d[idx] = o\n",
    "                ans.append(idx+1)\n",
    "        \n",
    "        return ans\n",
    "        \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 求以 obstacles[i] 结尾的最长非递减子序列的长度\n",
    "        # 贪心 + 二分\n",
    "        g = []\n",
    "        ans = []\n",
    "        for x in obstacles:\n",
    "            j = bisect_right(g, x)\n",
    "            ans.append(j + 1)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[j] = x\n",
    "        return ans\n",
    "\n",
    "\n",
    "        # 递推 O(n ** 2) TLE\n",
    "        # n = len(obstacles)\n",
    "        # f = [0] * n\n",
    "\n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j] <= obstacles[i]:\n",
    "        #             f[i] = max(f[i], f[j])\n",
    "        #     f[i] += 1\n",
    "        # return f\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        m = len(obstacles)\n",
    "        dp = []\n",
    "        res = []\n",
    "        for n in obstacles:\n",
    "            if not dp or dp[-1]<=n:\n",
    "                dp.append(n)\n",
    "                res.append(len(dp))\n",
    "            else:\n",
    "                loc = bisect_right(dp, n)\n",
    "                dp[loc] = n\n",
    "                res.append(loc+1)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        tails=[]\n",
    "        ans=[]\n",
    "        for num in obstacles:\n",
    "            i=0\n",
    "            j=len(tails)\n",
    "            while i<j:\n",
    "                m=(i+j)//2\n",
    "                if tails[m]<=num:i=m+1\n",
    "                else:j=m\n",
    "            if i==len(tails):tails.append(num)\n",
    "            else:tails[i]=num\n",
    "            ans.append(i+1)\n",
    "        return ans    \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        dp = []\n",
    "        res = []\n",
    "\n",
    "        for i in range(n):\n",
    "            j = bisect.bisect_right(dp, obstacles[i])\n",
    "            if j == len(dp):\n",
    "                dp.append(obstacles[i])\n",
    "            else:\n",
    "                dp[j] = obstacles[i]\n",
    "            res.append(j+1)\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        ans = []\n",
    "        d = []\n",
    "        for ob in obstacles:\n",
    "            if len(d) == 0 or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                index = bisect.bisect_right(d, ob)\n",
    "                ans.append(index + 1)\n",
    "                d[index] = ob\n",
    "        return ans            \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        d = []\n",
    "        ans = []\n",
    "        for ob in obstacles:\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                loc = bisect_right(d, ob)\n",
    "                d[loc] = ob\n",
    "                ans.append(loc + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        obs = []\n",
    "        for ob in obstacles:\n",
    "            pos = bisect.bisect_right(obs, ob)\n",
    "            if pos == len(obs):\n",
    "                obs.append(ob)\n",
    "            else:\n",
    "                obs[pos] = ob\n",
    "            ans.append(pos + 1)\n",
    "        return ans\n",
    "\n",
    "                \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        g = []\n",
    "        for i,x in enumerate(obstacles):\n",
    "            idx = bisect_right(g,x)\n",
    "            if idx == len(g):\n",
    "                g.append(x)\n",
    "            else:\n",
    "                g[idx] = x\n",
    "            ans.append(idx + 1)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = [] # 用一个单调列表存储递增数列\n",
    "        ans = [] \n",
    "        for ob in obstacles:\n",
    "            # 如果ob比前面所有的障碍物都高, 那么它将直接放在列表顶端\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            # 否则, 二分查找它的位置,并且把这个障碍物替换成新的障碍物\n",
    "            else:\n",
    "                location = bisect_right(d, ob)\n",
    "                ans.append(location + 1)\n",
    "                d[location] = ob\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "    # 二分法\n",
    "       n = len(obstacles)\n",
    "       g = [] \n",
    "       ans = []\n",
    "       for x in obstacles:\n",
    "           j = bisect_right(g, x)\n",
    "           if j == len(g):\n",
    "               g.append(x)\n",
    "               ans.append(len(g))\n",
    "           else:\n",
    "               g[j] = x\n",
    "               ans.append(j+1)\n",
    "       return ans\n",
    "\n",
    "    # 数组\n",
    "        # # 以nums[i]结尾的LIS（<=）\n",
    "        # n = len(obstacles)\n",
    "        # f = [0]*n\n",
    "        \n",
    "        # for i in range(n):\n",
    "        #     for j in range(i):\n",
    "        #         if obstacles[j] <= obstacles[i]:\n",
    "        #             f[i] = max(f[i],f[j])\n",
    "        #     f[i] +=1\n",
    "        # return f\n",
    "\n",
    "        # 记忆话\n",
    "        # @cache\n",
    "        # def dfs(i):\n",
    "        #     res = 0 #这里不需要判断边界条件，因为i<0的时候程序不会执行\n",
    "        #     for j in range(i):\n",
    "               \n",
    "        #         if obstacles[j]<=obstacles[i]:\n",
    "        #             res = max(res,dfs(j))\n",
    "        #     return res+1\n",
    "        \n",
    "        # return [dfs(i) for i in range(n)]\n",
    "        \n",
    "             "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # 就是求最长递增子序列,dp[i] 为以i为结尾的最长递增子序列\n",
    "        lenth = len(obstacles)\n",
    "        longst = []\n",
    "        # 必须用二分法,普通dp超时\n",
    "        result = []\n",
    "        for num in obstacles:\n",
    "            i = bisect_right(longst,num) # >=这里用right\n",
    "            if i == len(longst):\n",
    "                longst.append(num)\n",
    "            else:\n",
    "                longst[i] = num\n",
    "            result.append(i+1) # +1补一下个数\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d=[]\n",
    "        ans=[]\n",
    "        for ob in obstacles:\n",
    "            if not d or ob>=d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                loc=bisect_right(d,ob)\n",
    "                ans.append(loc+1)\n",
    "                d[loc]=ob\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        ans = [1 for _ in range(n)]\n",
    "\n",
    "        dp = [obstacles[0]]\n",
    "        for i in range(1, n):\n",
    "            if obstacles[i] >= dp[-1]:\n",
    "                dp.append(obstacles[i])\n",
    "                ans[i] = len(dp)\n",
    "            else:\n",
    "                # print(i, dp, obstacles[i])\n",
    "                t = bisect.bisect_right(dp, obstacles[i])\n",
    "                dp[t] = obstacles[i]\n",
    "                ans[i] = t + 1\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, nums: List[int]) -> List[int]:\n",
    "        n = len(nums)\n",
    "        g = []\n",
    "        ans = []\n",
    "        for x in nums:\n",
    "            j = bisect_right(g, x)\n",
    "            if j == len(g):\n",
    "                g.append(x)\n",
    "                ans.append(len(g))\n",
    "            else:\n",
    "                g[j] = x\n",
    "                ans.append(len(g[:j + 1]))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "from bisect import bisect_right\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n = len(obstacles)\n",
    "        uparr = [obstacles[0]]\n",
    "        ans = [1]\n",
    "        for i in range(1,n):\n",
    "            if obstacles[i]>=uparr[-1]:\n",
    "                uparr.append(obstacles[i])\n",
    "                ans.append(len(uparr))\n",
    "            else:\n",
    "                idx = bisect_right(uparr, obstacles[i])\n",
    "                uparr[idx] = obstacles[i]\n",
    "                ans.append(idx+1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        n=len(obstacles)\n",
    "        dp=list()\n",
    "        res=list()\n",
    "        for val in obstacles:\n",
    "            if not dp or val>=dp[-1]:\n",
    "                dp.append(val)\n",
    "                res.append(len(dp))\n",
    "            else:\n",
    "                index=bisect_right(dp,val)\n",
    "                res.append(index+1)\n",
    "                dp[index]=val\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, nums: List[int]) -> List[int]:\n",
    "       n = len(nums)\n",
    "       g = [] \n",
    "       ans = []\n",
    "       for x in nums:\n",
    "           j = bisect_right(g, x)\n",
    "           if j == len(g):\n",
    "               g.append(x)\n",
    "               ans.append(j+1)\n",
    "           else:\n",
    "               g[j] = x\n",
    "               ans.append(j+1)\n",
    "       return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        ans = []\n",
    "        g = []\n",
    "\n",
    "        def binary_search(info: List[int], x: int) -> int:\n",
    "            left = -1\n",
    "            right = len(info)\n",
    "            while left + 1 < right:\n",
    "                mid = (left + right) // 2\n",
    "                if info[mid] <= x:\n",
    "                    left = mid\n",
    "                else:\n",
    "                    right = mid\n",
    "            return right\n",
    "\n",
    "        for x in obstacles:\n",
    "            right = binary_search(g, x)\n",
    "            if right == len(g):\n",
    "                g.append(x)\n",
    "                ans.append(len(g))\n",
    "            else:\n",
    "                g[right] = x\n",
    "                ans.append(right + 1)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            # 这里需要改成 >=\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                # 将 300 题解中的二分查找改为 API 调用使得代码更加直观\n",
    "                # 如果是最长严格递增子序列，这里是 bisect_left\n",
    "                # 如果是最长递增子序列，这里是 bisect_right\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        \n",
    "        return ans\n",
    "\n",
    "# 作者：力扣官方题解\n",
    "# 链接：https://leetcode.cn/problems/find-the-longest-valid-obstacle-course-at-each-position/solutions/922831/zhao-chu-dao-mei-ge-wei-zhi-wei-zhi-zui-pb8mu/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        d = list()\n",
    "        ans = list()\n",
    "        for ob in obstacles:\n",
    "            if not d or ob >= d[-1]:\n",
    "                d.append(ob)\n",
    "                ans.append(len(d))\n",
    "            else:\n",
    "                loc = bisect_right(d, ob)\n",
    "                ans.append(loc + 1)\n",
    "                d[loc] = ob\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def longestObstacleCourseAtEachPosition(self, obstacles: List[int]) -> List[int]:\n",
    "        # q表示长度为 iii 的最长上升子序列的末尾元素的最小值\n",
    "        q = list()\n",
    "        res = list()\n",
    "        for ob in obstacles:\n",
    "            if not q or ob >= q[-1]:\n",
    "                q.append(ob)\n",
    "                res.append(len(q))\n",
    "            else:\n",
    "                # 将当前的ob插入到它前面的队列中。只有比当前ob高的是重要的，否则就可以忽略。\n",
    "                idx = bisect_right(q, ob)\n",
    "                res.append(idx + 1)\n",
    "                q[idx] = ob\n",
    "        return res\n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
